home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / libs / sphigs / sph_dos.lha / dos / sphsrc / sph_opti.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-26  |  3.4 KB  |  120 lines
  1. #include "HEADERS.h"
  2. #include "sphigslocal.h"
  3.  
  4. /**
  5. One simple form of optimization is to record, for each view V, a list of the structures
  6. that are subordinates of view V.  This data must be updated in the following ways:
  7.  
  8.  
  9. WHEN A STRUCTURE S IS POSTED TO VIEW V:
  10.     Add S to the subord-list for view V.
  11.     Traverse the network rooted at S:
  12.         Add each encountered structure to the subord-list for view V.
  13.         
  14. WHEN A STRUCTURE S IS UNPOSTED FROM VIEW V:
  15.     Completely recalculate view V's subord-list.
  16.         
  17. WHEN A STRUCTURE P BECOMES A NEW CHILD OF STRUCTURE S:
  18.     Create a temporary subord-list, initially clear.
  19.     Add P to the temp list.
  20.     Traverse the network rooted at P:
  21.         Add each encountered structure to the temp subord-list.
  22.     For each view V:
  23.         If structure S is a subord of view V:
  24.            "OR" the temp subord-list with view V's current subord-list.
  25.             
  26. WHEN A STRUCTURE S IS EDITED IN SUCH A WAY THAT IT POSSIBLY LOST A CHILD:
  27.     For each view V:
  28.         If structure S is posted to view V:
  29.             Completely recalculate view V's subord-list.
  30.             
  31. Here's the algorithm for completely recalculating view V's subord list:
  32.     Clear the subord-list for view V.
  33.     For each structure P still posted to view V:
  34.         Traverse the network rooted at P:
  35.             Add each encountered structure to the subord-list for view V.
  36.  
  37. **/
  38.             
  39.  
  40. static substruct_bitstring temp_descendent_list = NULL;
  41.  
  42.  
  43. /** MERGE DESCENDENT LIST
  44. Uses an optimization algorithm to avoid unnecessary re-traversal.
  45. Warning: assumes bit #sid already set!
  46. **/
  47. static void MergeDescendentList (int sid)
  48. {
  49.    register int s;
  50.    
  51.    for (s=0; s<=MAX_STRUCTURE_ID; s++)
  52.       /* IF STRUCTURE s IS AN IMMEDIATE CHILD OF sid THEN... */
  53.       if (TestBit(SPH__structureTable[sid].child_list, s))
  54.          /* RECURSE ONLY IF STRUCTURE s IS NOT YET RECORDED */
  55.          if ( ! TestBit(temp_descendent_list, s)) {
  56.         SetBit (temp_descendent_list, s);
  57.             MergeDescendentList (s);
  58.          }
  59. }
  60.  
  61.  
  62. static void CalculateDescendentListForOneStructure (int struct_ID)
  63. {
  64.    
  65.    ClearBitstring (&temp_descendent_list);
  66.    SetBit (temp_descendent_list, struct_ID);
  67.    MergeDescendentList (struct_ID);
  68. }
  69.  
  70.  
  71. static void CalculateDescendentListForView (view_spec *vs)
  72. {
  73.    root_header *rptr;
  74.    
  75.    ClearBitstring (&temp_descendent_list);
  76.    
  77.    for (rptr=vs->highestOverlapNetwork; rptr; 
  78.     rptr=rptr->nextLowerOverlapRoot) {    
  79.       SetBit (temp_descendent_list, rptr->root_structID);
  80.       MergeDescendentList (rptr->root_structID);
  81.    }
  82. }
  83.  
  84.  
  85.  
  86. void VIEWOPT__afterNewPosting (view_spec *v, int struct_ID)
  87. {
  88.    CalculateDescendentListForOneStructure (struct_ID);
  89.    MergeBitstring (v->descendent_list, temp_descendent_list);
  90. }
  91.  
  92.  
  93. void VIEWOPT__afterUnposting (view_spec *v, int struct_ID)
  94. {
  95.    CalculateDescendentListForOneStructure (struct_ID);
  96.    MergeBitstring (v->descendent_list, temp_descendent_list);
  97. }
  98.  
  99.  
  100. void VIEWOPT__newExecuteStructure (int ID_of_new_parent, int ID_of_new_child)
  101. {
  102.    register int v;
  103.    
  104.    CalculateDescendentListForOneStructure (ID_of_new_child);
  105.    for (v=0; v<=MAX_VIEW_INDEX; v++)
  106.       if (TestBit(SPH_viewTable[v].descendent_list, ID_of_new_parent))
  107.      MergeBitstring 
  108.         (SPH_viewTable[v].descendent_list, temp_descendent_list);
  109. }
  110.  
  111.  
  112. void VIEWOPT__afterChildLoss (int ID_of_changed_parent)
  113. {
  114.    register int v;
  115.    
  116.    for (v=0; v<=MAX_VIEW_INDEX; v++)
  117.       if (TestBit(SPH_viewTable[v].descendent_list, ID_of_changed_parent))
  118.      CalculateDescendentListForView (&(SPH_viewTable[v]));
  119. }
  120.